from itertools import chain
from typing import List


class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        # 入度计数
        n = len(edges)
        indegrees = [0] * (n+1)
        candidates = []
        for u, v in edges:
            if indegrees[v] == 0:
                indegrees[v] = u
            else:
                candidates = [[indegrees[v], v], [u, v]]
                break

        # UFS
        parents = list(range(n+1))
        sizes = [1] * (n+1)

        def find(x):
            if parents[x] != x:
                parents[x] = find(parents[x])
            return parents[x]

        def union(x, y):
            x = find(x)
            y = find(y)
            if x == y:
                return True
            if sizes[x] < sizes[y]:
                x, y = y, x
            parents[y] = x
            sizes[x] += sizes[y]
            return False

        ordered_edges = chain((e for e in edges if e not in candidates), candidates)
        for u, v in ordered_edges:
            if union(u, v):
                return [u, v]


def brutal_solve(edges):
    def solve_inner(edges):
        from copy import deepcopy
        from algorithm import UnionFindSet
        edges = deepcopy(edges)
        def is_tree(edges):
            # 无环、联通、无重父
            n = len(edges) + 1
            parents = {}
            for u, v in edges:
                if v in parents:
                    return False
                parents[v] = u
            ufs = UnionFindSet(n)
            for u, v in edges:
                if ufs.union(u, v):
                    return False
            connected = all(ufs.find(x) == ufs.find(0) for x in range(n))
            return connected

        n = len(edges)
        for i in range(n-1, -1, -1):
            e = edges.pop(i)
            if is_tree(edges):
                return list(e)
            edges.insert(i, e)

    u,v = solve_inner([[u-1,v-1] for u, v in edges])
    return [u+1, v+1]

def random_test():
    import random
    from algorithm import random_tree
    for _ in range(100000):
        n = random.randint(3, 8)
        edges = random_tree(n_nodes=n, shuffle_nodes=True)
        extra_edge = random.sample(range(n), 2)
        edges += [extra_edge]
        random.shuffle(edges)
        edges = [[u+1, v+1] for u, v in edges]
        res1 = Solution().findRedundantDirectedConnection(edges)
        res2 = brutal_solve(edges)
        if res1 != res2:
            print(edges, res1, res2)
random_test()


edges = [[2,1],[3,1],[4,2],[1,4]]
solution = Solution()
result = solution.findRedundantDirectedConnection(edges)
print(result)


edges = [[3,1], [1,2], [2,3], [2,4]]
solution = Solution()
result = solution.findRedundantDirectedConnection(edges)
print(result)


edges = [[1,2], [1,3], [2,4], [3,4]]
solution = Solution()
result = solution.findRedundantDirectedConnection(edges)
print(result)

edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
solution = Solution()
result = solution.findRedundantDirectedConnection(edges)
print(result)


